We consider the problem of generating automatic code given sample input-output pairs. We train a neural network to map from the current state and the outputs to the program's next statement. The neural network optimizes multiple tasks concurrently: the next operation out of a set of high level commands, the operands of the next statement, and which variables can be dropped from memory. Using our method we are able to create programs that are more than twice as long as existing state-of-the-art solutions, while improving the success rate for comparable lengths, and cutting the run-time by two orders of magnitude. Our code, including an implementation of various literature baselines, is publicly available at https://github.com/amitz25/PCCoder

The paper presents a modification of a previous baseline method in the application area of inductive program synthesis (IPS). This new architecture, PCCoder, shows some considerable improvement over DeepCoder, the baseline main method it compared against. Within the setting of IPS, the goal of the model is, provided with some input/output examples meant to represent a partial program specification, output a program that successfully maps from input to output for each I/O example in the set. A program is considered correct if it accomplishes the mapping on all provided I/O pairs (there is no notion of generalization to unseen I/O pairs as sometimes done in previous work, especially in string processing domains). The input/output pairs consist of integers, and the program is constructed from the relatively expressive Domain Specific Language defined in the DeepCoder paper.

Program synthesis aims to automatically construct human-readable programs that satisfy given task specifications, such as input/output pairs or demonstrations. Recent works have demonstrated encouraging results in a variety of domains, such as string transformation, tensor manipulation, and describing behaviors of embodied agents. Most existing program synthesis methods are designed to synthesize programs from scratch, generating a program token by token, line by line. This fundamentally prevents these methods from scaling up to synthesize programs that are longer or more complex. In this work, we present a scalable program synthesis framework that instead synthesizes a program by hierarchically composing programs. Specifically, we first learn a task embedding space and a program decoder that can decode a task embedding into a program. Then, we train a high-level module to comprehend the task specification (e.g., input/output pairs or demonstrations) from long programs and produce a sequence of task embeddings, which are then decoded by the program decoder and composed to yield the synthesized program. We extensively evaluate our proposed framework in a string transformation domain with input/output pairs. The experimental results demonstrate that the proposed framework can synthesize programs that are significantly longer and more complex than the programs considered in prior program synthesis works. Website at https://thoughtp0lice.github.io/hnps_web/

We consider the problem of generating automatic code given sample input-output pairs. We train a neural network to map from the current state and the outputs to the program's next statement. The neural network optimizes multiple tasks concurrently: the next operation out of a set of high level commands, the operands of the next statement, and which variables can be dropped from memory. Using our method we are able to create programs that are more than twice as long as existing state-of-the-art solutions, while improving the success rate for comparable lengths, and cutting the run-time by two orders of magnitude. Our code, including an implementation of various literature baselines, is publicly available at https://github.com/amitz25/PCCoder

This white paper was prepared by the participants of the fall 2016 long program Understanding Many-Particle Systems with Machine Learning. Interactions between many constituent particles, i.e. quarks, electrons, atoms, molecules, or materials, generally give rise to collective or emergent phenomena in matter. Even when the interactions between the particles are well defined and the governing equations of the system are understood, the collective behavior of the system as a whole does not trivially emerge from these equations. Despite many decades of prominent work on interacting many-particle (MP) systems, the problem of N interacting particles is not exactly soluble. In fact, computational complexity typically increases exponentially with N.